﻿//// set
//#ifndef __SGI_STL_INTERNAL_TREE_H
//#include <stl_tree.h>
//#endif
//#include <stl_set.h>
//#include <stl_multiset.h>
//// map
//#ifndef __SGI_STL_INTERNAL_TREE_H
//#include <stl_tree.h>
//#endif
//#include <stl_map.h>
//#include <stl_multimap.h>
//// stl_set.h
//template <class Key, class Compare = less<Key>, class Alloc = alloc>
//class set {
//public:
//	// typedefs:
//	typedef Key key_type;
//	typedef Key value_type;
//private:
//	typedef rb_tree<key_type, value_type,
//		identity<value_type>, key_compare, Alloc> rep_type;
//	rep_type t; // red-black tree representing set
//};
//// stl_map.h
//template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
//class map {
//public:
//	// typedefs:
//	typedef Key key_type;
//	typedef T mapped_type;
//	typedef pair<const Key, T> value_type;
//private:
//	typedef rb_tree<key_type, value_type,
//		select1st<value_type>, key_compare, Alloc> rep_type;
//	rep_type t; // red-black tree representing map
//};
//// stl_tree.h
//struct __rb_tree_node_base
//{
//	typedef __rb_tree_color_type color_type;
//	typedef __rb_tree_node_base* base_ptr;
//	color_type color;
//	base_ptr parent;
//	base_ptr left;
//	base_ptr right;
//};
//// stl_tree.h
//template <class Key, class Value, class KeyOfValue, class Compare, class Alloc
//	= alloc>
//class rb_tree {
//protected:
//	typedef void* void_pointer;
//	typedef __rb_tree_node_base* base_ptr;
//	typedef __rb_tree_node<Value> rb_tree_node;
//	typedef rb_tree_node* link_type;
//	typedef Key key_type;
//	typedef Value value_type;
//public:
//	// insert⽤的是第⼆个模板参数做形参
//	pair<iterator, bool> insert_unique(const value_type& x);
//	// erase和find⽤第⼀个模板参数做形参
//	size_type erase(const key_type& x);
//	iterator find(const key_type& x);
//protected:
//	size_type node_count; // keeps track of size of tree
//	link_type header;
//};
//template <class Value>
//struct __rb_tree_node : public __rb_tree_node_base
//{
//	typedef __rb_tree_node<Value>* link_type;
//	Value value_field;
//};

//// 源码中pair⽀持的<重载实现
//template <class T1, class T2>
//bool operator< (const pair<T1, T2>& lhs, const pair<T1, T2>& rhs)
//{
//	return lhs.first < rhs.first || (!(rhs.first < lhs.first) &&
//		lhs.second < rhs.second);
//}
//// Mymap.h
//namespace sy
//{
//	template<class K, class V>
//	class map
//	{
//		struct MapKeyOfT
//		{
//			const K& operator()(const pair<K, V>& kv)
//			{
//				return kv.first;
//			}
//		};
//	public:
//		bool insert(const pair<K, V>& kv)
//		{
//			return _t.Insert(kv);
//		}
//	private:
//		RBTree<K, pair<K, V>, MapKeyOfT> _t;
//	};
//}
//// Myset.h
//namespace sy
//{
//	template<class K>
//	class set
//	{
//		struct SetKeyOfT
//		{
//			const K& operator()(const K& key)
//			{
//				return key;
//			}
//		};
//	public:
//		bool insert(const K& key)
//		{
//			return _t.Insert(key);
//		}
//	private:
//		RBTree<K, K, SetKeyOfT> _t;
//	};
//}
//// RBTree.h
//enum Colour
//{
//	RED,
//	BLACK
//};
//template<class T>
//struct RBTreeNode
//{
//	T _data;
//	RBTreeNode<T>* _left;
//	RBTreeNode<T>* _right;
//	RBTreeNode<T>* _parent;
//	Colour _col;
//	RBTreeNode(const T& data)
//		: _data(data)
//		, _left(nullptr)
//		, _right(nullptr)
//		, _parent(nullptr)
//	{}
//};
//// 实现步骤：
//// 1、实现红⿊树
//// 2、封装map和set框架，解决KeyOfT
//// 3、iterator
//// 4、const_iterator
//// 5、key不⽀持修改的问题
//// 6、operator[]
//template<class K, class T, class KeyOfT>
//class RBTree
//{
//private:
//	typedef RBTreeNode<T> Node;
//	Node* _root = nullptr;
//public:
//	bool Insert(const T& data)
//	{
//		if (_root == nullptr)
//		{
//			_root = new Node(data);
//			_root->_col = BLACK;
//			return true;
//		}
//		KeyOfT kot;
//		Node* parent = nullptr;
//		Node* cur = _root;
//		while (cur)
//		{
//			if (kot(cur->_data) < kot(data))
//			{
//				parent = cur;
//				cur = cur->_right;
//			}
//			else if (kot(cur->_data) > kot(data))
//			{
//				parent = cur;
//				cur = cur->_left;
//			}
//			else
//			{
//				return false;
//			}
//		}
//		cur = new Node(data);
//		Node* newnode = cur;
//		// 新增结点。颜⾊给红⾊
//		cur->_col = RED;
//		if (kot(parent->_data) < kot(data))
//		{
//			parent->_right = cur;
//		}
//		else
//		{
//			parent->_left = cur;
//		}
//		cur->_parent = parent;
//		//...
//		return true;
//	}
//};

//struct __rb_tree_base_iterator
//{
//	typedef __rb_tree_node_base::base_ptr base_ptr;
//	base_ptr node;
//	void increment()
//	{
//		if (node->right != 0) {
//			node = node->right;
//			while (node->left != 0)
//				node = node->left;
//		}
//		else {
//			base_ptr y = node->parent;
//			while (node == y->right) {
//				node = y;
//				y = y->parent;
//			}
//			if (node->right != y)
//				node = y;
//		}
//	}
//	void decrement()
//	{
//			if (node->color == __rb_tree_red &&
//				node->parent->parent == node)
//				node = node->right;
//			else if (node->left != 0) {
//				base_ptr y = node->left;
//				while (y->right != 0)
//					y = y->right;
//				node = y;
//			}
//			else {
//				base_ptr y = node->parent;
//				while (node == y->left) {
//					node = y;
//					y = y->parent;
//				}
//				node = y;
//			}
//	}
//};
//template <class Value, class Ref, class Ptr>
//struct __rb_tree_iterator : public __rb_tree_base_iterator
//{
//	typedef Value value_type;
//	typedef Ref reference;
//	typedef Ptr pointer;
//	typedef __rb_tree_iterator<Value, Value&, Value*> iterator;
//	__rb_tree_iterator() {}
//	__rb_tree_iterator(link_type x) { node = x; }
//	__rb_tree_iterator(const iterator& it) { node = it.node; }
//	reference operator*() const { return link_type(node)->value_field; }
//#ifndef __SGI_STL_NO_ARROW_OPERATOR
//	pointer operator->() const { return &(operator*()); }
//#endif /* __SGI_STL_NO_ARROW_OPERATOR */
//	self& operator++() { increment(); return *this; }
//	self& operator--() { decrement(); return *this; }
//	inline bool operator==(const __rb_tree_base_iterator& x,
//		const __rb_tree_base_iterator& y) {
//		return x.node == y.node;
//	}
//	inline bool operator!=(const __rb_tree_base_iterator& x,
//		const __rb_tree_base_iterator& y) {
//		return x.node != y.node;
//	}